The invention relates to creating an electronic image in a palette based file format in which the image's colors are stored in a look-up table or color palette in the output image file. Common examples of palette based file formats are the Graphical Interchange Format (GIF) and the 8-bit Portable Network Graphics format (PNG8).
Electronic images are often transmitted from one user to another. The speed of transmission depends in part on the size of the image being transmitted, and can be reduced by reducing the image's size. One way to reduce an image's size is to reduce the number of colors used to paint the image. For example, an image painted with 24-bit (true) color and containing millions of colors can be reduced by converting it to a palette-based output file containing only a small fraction of the source image's true colors. To generate the palette-based output file, every color in the source image is mapped to a nearest color that is available in the palletized file's color palette. Since the color palette typically contains only 256 unique colors, much of the color information in the source image is lost when converting it to a palette-based output file.
To partially compensate for this loss in color fidelity, applications converting images to a palette-based file format frequently simulate colors which are not available in the output image's color palette using a process called dithering. Dithering simulates the colors which are not available in the output image's color palette by creating pixel patterns of related colors which are available. These pixel patterns are blended in the mind of an observer, and create the illusion of seeing many of the unavailable colors. Various methods of dithering are known. For example, the error diffusion method operates by painting each pixel in the output image with a paint color available in that image's color palette that is nearest to a target color. The target color is the sum of the true color of a corresponding pixel in the source image and a diffusive color error obtained from one or more previous pixels in the converted output image, where the diffusive color error is a measure of the difference between the paint and target colors in previous pixels in the converted output image.
Another way of reducing an image's size (in addition to palletizing it) is to compress the image using one of a number of known compression algorithms. The algorithm typically used to compress palletized color images is the Lempel-Ziv-Welch (LZW) compression algorithm. The LZW algorithm works by finding repetitive sequences in the source image, storing the repetitive sequences in a compression table with smaller identifying code words, and writing the identifying code words and the compression table to the compressed output file. The LZW compression algorithm works best (compresses most) when the source file contains long repetitive sequences. For example, the LZW compression algorithm works best with color images that contain regions of pixels having the same color.
When a color image is converted to a palette-based file format without dithering, whole regions of the image are often mapped to the same color palette color, because the color variation among pixels in a given region is often smaller than the color difference between neighboring colors in the color palette. Thus, color images which are converted to palette-based images without dithering can often be significantly compressed by the LZW compression algorithm. Conversely, when a color image is dithered while being converted to a palette-based file format, nearly every pixel in the converted image contains a different color table color because of the color error diffusion introduced by the dithering algorithm. As a result, color images converted to palette-based images while being dithered are much less compressible than color images converted to palette-based images without being dithered.